函数相关的证明就不说了,直接下定义。
有向图游戏:
把游戏进行中的局面视作一个状态,在当前的状态和进行某些操作后得到的新状态之间连一条有向边,整个图就构成了一个有向图。
函数:
规定是在集合中最小的,没有出现的非负整数。
函数:
在有向图游戏中,从状态出去的边有条,得到的新状态分别记作,......,则。特别的,对于整张图的函数值为起点的值。
多个有向图游戏的和:
设共有个有向图游戏,记作,,...,。每次是在个有向图游戏里选一个游戏走一步,记是所有有向图游戏的和,则。
游戏判据:
有向图游戏的某个局面必胜,当且仅当当前节点的值大于。
有向图游戏的某个局面必败,当且仅当当前节点的值为。
对于多个有向图游戏的和,同样满足。
[POJ 2311]Cutting game
题目大意:有一张的格子纸,每次可以沿竖直或水平方向的线剪开。第一个剪出大小为的人胜利。问先手是否必胜。
数据范围:
每次切一下之后,会使得剩下的有向图游戏增多,可以根据上面的多个有向图游戏的和的结论来计算。不过要注意抠掉边界情况,当剩下的局面里有长度为的条时,就一定失败了。具体在做记忆华搜索的时候,可以通过减少枚举范围来做到。本题的函数公式也比较显然,这里直接给出:
注意,用于记忆化的数组不必每次都重置,对于某个之前搜过的局面,之后的游戏里如果碰到了不会影响游戏状态。如果每次都重置会导致复杂度过高而TLE。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
typedef long long ll;
const int N = 205;
int n,m;
int mem[N][N];
int SG(int n,int m)
{
if(mem[n][m] != -1) return mem[n][m];
set<int> tb;
for(int i = 2;n - i >= 2;++i) tb.insert(SG(i,m) ^ SG(n - i,m));
for(int i = 2;m - i >= 2;++i) tb.insert(SG(n,i) ^ SG(n,m - i));
int res = 0;
while(tb.count(res)) ++res;
return mem[n][m] = res;
}
int main()
{
memset(mem,-1,sizeof mem);
while(scanf("%d%d",&n,&m) == 2)
{
if(SG(n,m)) puts("WIN");
else puts("LOSE");
}
return 0;
}